package 数组.KMP.KMP查找算法;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/2/13 13:41
 * @description:
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        String str = "abcabca";
        String pattern = "ababab";
        System.out.println(search(str, pattern));
    }

    public static int search(String str,String pattern){
        char[] strs = str.toCharArray();
        char[] patterns = pattern.toCharArray();
        int L = strs.length,N = patterns.length,i = 0,j = 0;
        if (N < 1) return 0;
        if (L < N) return -1;
        int[] lps = lps(pattern);
        while (i < L){
            if (strs[i] == patterns[j]){
                ++i;
                ++j;
                if (j == N) return i - N;
            }else if (j > 0){
                j = lps[j - 1];
            }else {
                ++i;
            }
        }
        return -1;
    }

    //KMP算法中的NEXT数组
    private static int[] lps(String pattern) {
        int j = 0,i = 1,L = pattern.length();
        int[] res = new int[L];
        char[] chars = pattern.toCharArray();
        while (i < L){
            if (chars[i] == chars[j]) res[i++] = ++j;
            else {
                int temp = i -1;
                while (temp > 0){
                    int prevLPS = res[temp];
                    if (chars[i] == chars[prevLPS]){
                        res[i++] = prevLPS + 1;
                        j = prevLPS;
                        break;
                    }else {
                        temp = prevLPS - 1;
                    }
                }
                if (temp <= 0){
                    res[i++] = 0;
                    j = 0;
                }
            }
        }
        return res;
    }
}
